# encoding: utf-8
import insertion_sort
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: bucket_sort.py 
@time: 2019/7/2 9:51
"""
'''
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
为了使桶排序更加高效，我们需要做到这两点：
1.在额外空间充足的情况下，尽量增大桶的数量
2.使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
'''

def bucketSort(nums, defaultBucketSize = 5):
    maxVal, minVal = max(nums), min(nums)
    bucketSize = defaultBucketSize
    # 如果没有指定桶的大小，则默认为5
    bucketCount = (maxVal - minVal) // bucketSize + 1
    # 数据分为bucketCount组
    buckets = []
    # 二维桶
    for i in range(bucketCount):
        buckets.append([])
    # 利用函数映射将各个数据放入对应的桶中
    for num in nums:
        buckets[(num - minVal) // bucketSize].append(num)
    nums.clear()
    # 清空nums
    # 对每一个二维桶中的元素进行排序
    for bucket in buckets:
        insertion_sort.insertionSort(bucket)
        # 假设使用插入排序
        nums.extend(bucket)
        # 将排序好的桶依次放入到nums中
    return nums

# Example use
nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
print(bucketSort(nums))